/**
 * 1.把无序数组构建成二叉堆，需要从小到大排序，则构建成最大堆；需要从大到小排序，则构建成最小堆
 * 2. 循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶元素
 */


class HeapOperator {
    constructor(array){
        this.array=array;
        this.buildHeap();
    }
    add(item){
        this.array.push(item);
        this.upAdjust();
    }
    /**
     * 上浮调整
     */
    upAdjust() {
        let childIndex = this.array.length-1;
        let parentIndex;
        if(childIndex%2==0){// 右孩子节点
            parentIndex = (childIndex-2)/2;
        }else{
            parentIndex = (childIndex-1)/2;
        }
        // temp保存插入的叶子节点值，用于最后的赋值
        let temp = this.array[childIndex];
        while (childIndex >= 0 && temp > this.array[parentIndex])
        {
            //无需真正交换，单向赋值即可
            this.array[childIndex] = this.array[parentIndex];
            childIndex = parentIndex;
            if(childIndex%2==0){// 右孩子节点
                parentIndex = (childIndex-2)/2;
            }else{
                parentIndex = (childIndex-1)/2;
            }
        }
        this.array[childIndex] = temp;
    }

     /**
     * 下沉调整
     * @param parentIndex    要下沉的父节点
     * @param length    堆的有效大小
     */
    downAdjust(parentIndex,length) {
        // temp保存父节点值，用于最后的赋值
        let temp = this.array[parentIndex];
        let childIndex = 2 * parentIndex + 1;
        while (childIndex < length) {
            // 如果有右孩子，且右孩子小于左孩子的值，则定位到右孩子
            if (childIndex + 1 < length && this.array[childIndex + 1] > this.array[childIndex]) {
                childIndex++;
            }
            // 如果父节点大于任何一个孩子的值，直接跳出
            if (temp >= this.array[childIndex])
                break;
            //无需真正交换，单向赋值即可
            this.array[parentIndex] = this.array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * childIndex + 1;
        }
        this.array[parentIndex] = temp;
    }

    /**
     * 构建堆
     */
    buildHeap() {
        // 从最后一个非叶子节点开始，依次下沉调整
        for (let i = (this.array.length-2)/2; i >= 0; i--) {
            this.downAdjust(i, this.array.length);
        }
    }
}


function heapSort(array) {
    let heap = new HeapOperator(array);
    for (let i = heap.array.length - 1; i >= 0; i--) {
        // 交换堆顶元素和末尾元素
        let temp = heap.array[0];
        heap.array[0] = heap.array[i];
        heap.array[i] = temp;
        // 下沉调整
        heap.downAdjust(0, i);
    }
    return heap.array;
}

let result = heapSort([22,3,2,6,5,7,8,9,10,7])

console.log(result);

